Data is often compressed in order to reduce computer memory requirements or to reduce transmission time. One popular data compression technique may be referred to as xe2x80x9centropy codingxe2x80x9d.
Huffman coding is one example of an entropy coding technique. A Huffman encoder will typically utilize a Huffman statistical model to convert a string of tokens into a series of variable length entropy codes. The Huffman encoder operates to assign short entropy codes to the tokens that occur most often and longer code words to the tokens that occur least often. The code words that are used in Huffman encoding are typically obtained from one or more tables, known as Huffman Tables.
While prior art entropy coding techniques have proven to be very useful, improvements in these techniques are always needed in order to reduce the memory requirements of computing systems as well as to improve the speed at which data can be communicated from one computer to another.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of the example the principles of the invention.
The present invention may be implemented as a method of encoding a string of tokens. In one embodiment, the string of tokens includes a first group of tokens that immediately follow a token having a first value. The method includes the step of generating a Huffman encoded string by, at least in part, Huffman encoding the first group based upon the local frequencies of the first group.
The present invention may also be implemented as an apparatus for encoding a string of tokens. In one embodiment, the apparatus is operable to identify a first group of tokens in the string. The first group of tokens being those tokens in the string that immediately follow a token having a first value. The apparatus is further operable to assign a Huffman codeword to each token value that occurs in the first group based upon the local frequencies of the first group.
The present invention may also be implemented as a program storage medium. In one embodiment, the program storage medium embodies a program of instruction executable by a computer to perform method steps for encoding a string of tokens. The string of tokens includes a first group of interspersed tokens each having a first value. The method steps may include identifying a second group of tokens in the string each immediately following a unique one of tokens in the first group; and Huffman encoding the string in part by Huffman encoding the second group of tokens based upon the local frequencies of the second group.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.